package com.origin.niuke.string;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 字符串解码
 * 给一个加密过的字符串解码，返回解码后的字符串。
 * 加密方法是：k[c] ，表示中括号中的 c 字符串重复 k 次，例如 3[a] 解码结果是 aaa ，保证输入字符串符合规则。
 * 不会出现类似 3a , 3[3] 这样的输入。
 * 输入："3[3[b]]"
 * 返回值："bbbbbbbbb"
 * 算法：递归、栈
 * 数字的后一个是 [, ] 的前一个是字母
 *
 * @author yezh
 * @date 2023/2/12 22:01
 */
public class NC199 {

    public String decodeString(String s) {
        String ans = "";
        int num = 0;
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<String> alp = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
            else if (c >= 'a' && c <= 'z') ans += c;
            else if (c == '[') {
                nums.addFirst(num); alp.addFirst(ans);
                num = 0; ans = "";
            } else {
                String tmp = "";
                int cnt = nums.pollFirst();
                while (cnt-- > 0) tmp += ans;
                ans = alp.pollFirst() + tmp;
            }
        }
        return ans;
    }

}